/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
/*
思路:
1. 快指针先走k步
2. 慢指针和快指针一起走，一次走一步
3. 快指针走到空，慢指针走到都k个节点
1 2 3 ···· N
1 2 3 k····N
快指针第二步开始 走N-k步
慢指针从头开始走n-k步 就是倒数第k步
*/
int kthToLast(struct ListNode* head, int k) {
    struct ListNode* slow = head, *fast = head;
    while(k--)
    {
        fast = fast->next;
    }
    while(fast)
    {
        fast = fast->next;
        slow = slow->next;
    }
    return slow->val;
}